Many hardware designs, such as bus protocols, coherent fabrics, memory sub-systems, and arithmetic datapaths, can have multiple (sometimes hundreds or thousands of) transactions “in-flight” at any point in time. A transaction is an exchange or interaction of data between start and end points of the design. Typically a transaction originates from a master (e.g. the requestor) and is sent to a slave for processing. For example, a master may send a request to read from, or write to, a memory or a cache (slave). A transaction is “in-flight” if it has been accepted for processing at an input interface of the slave and has not been issued out on an output interface of the slave. Accordingly, when a transaction first appears on an input interface of the slave it becomes in-flight and it remains in-flight until the transaction is issued out on an output interface of the slave. Such hardware designs are referred to as multi-transactional hardware designs.
Often multiple in-flight transactions need to access the same resource, such as a cache, arbiter, memory etc. which can create hazards. A hazard is a condition that occurs when more than one transaction (originating from the same or different requestors) tries to gain access to a shared resource (e.g. memory) at the same time. For example, if there is a write transaction and a read transaction to the same memory address, if the write is issued before the read, then the expected behavior is that the write should be completed before the read so that the read will get the new value written by the write. If, however, the read is completed before the write then the read will get the old value instead of the new value resulting in a hazard.
To eliminate hazards the hardware may be designed to implement an ordering on the transactions. This typically involves assigning to the transactions a unique identifier and using a hardware data structure to track the transactions and enforce an order using the unique identifiers. For example, the hardware data structure may ensure that when transaction requests (e.g. read/write requests) are issued on an interface that the corresponding responses (e.g. data payloads) come back in the same order in which the transaction requests were issued.
The most commonly used hardware data structure for tracking ordered transactions is a FIFO (First In First Out) data structure which uses a two-dimensional array and multiple pointers (e.g. a read pointer and a write pointer) to keep track of data in the array. However, formal verification using a FIFO to track ordered transactions is difficult.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known data structures for tracking ordered transactions.